package 回溯;

import java.util.Scanner;

// 深度优先算法——一条路走到黑

/**
 * Dfs(当前这一步的处理逻辑)
 * {
 *         1. 判断边界，是否已经一条道走到黑了：向上回退
 *         2. 尝试当下的每一种可能
 *         3. 确定一种可能之后，继续下一步 Dfs(下一步)
 * }
 */

public class DFS {
    public static void DFS(int[] book, int[] box, int idx, int n) {
        // 边界
        if(idx == n+1) {
            for (int i = 1;i <= n; i++) {
                System.out.print(box[i] + " ");
            }
            System.out.println();
            return; // 向上回退
        }
        // 尝试每一个可能，也就是让每一张牌都做一次第一
        for (int i = 1; i <= n ; i++) {
            if(book[i] == 0) { //第i号牌仍在手上
                box[idx] = i;  //放入这张牌
                book[i] = 1;   //放了
                // 处理下一个盒子
                DFS(book, box, idx + 1, n);
                // 从下一个盒子回退到当前盒子，取出当前盒子的牌
                book[i] = 0;
            }
        }
    }
//    从上面的代码可以看出，深度优先搜索的关键是解决"当下该如何做"，下一步的做法和当下的做法是一样的。"当下
//    如何做"一般是尝试每一种可能，用for循环遍历，对于每一种可能确定之后，继续走下一步，当前的剩余可能等到从
//    下一步回退之后再处理。我们可以抽象出深度优先搜索的模型。

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] book = new int[n+1];
        int[] box = new int[n+1];
        DFS(book,box,1,n);
    }
}
